package com.study.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode-cn.com/problems/sudoku-solver/submissions/
public class Solution_37 {
    public void solveSudoku(char[][] board) {
        List<List<Integer>> blanks = getBlanks(board);
        solveSudoku(board, blanks, 0);

    }

    public boolean solveSudoku(char[][] board, List<List<Integer>> blanks, int index) {
        if (index >= blanks.size()) {
            return true;
        }
        int row = blanks.get(index).get(0);
        int col = blanks.get(index).get(1);
        String nextNumbers = findNextNumbers(board, row, col);
        if (nextNumbers.length() == 0) return false;
        for (int i = 0; i < nextNumbers.length(); i++) {
            board[row][col] = nextNumbers.charAt(i);
            if (solveSudoku(board, blanks, index + 1)) {
                return true;
            }
            board[row][col] = '.';
        }
        return false;
    }

    public List<List<Integer>> getBlanks(char[][] board) {
        List<List<Integer>> blanks = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    blanks.add(Arrays.asList(i, j));
                }
            }
        }
        return blanks;
    }

    public String findNextNumbers(char[][] board, int row, int col) {
        String res = "123456789";
        for (int i = 0; i < 9; i++) {
            res = res.replace(board[row][i] + "", "");
            res = res.replace(board[i][col] + "", "");
        }
        row = row / 3;
        col = col / 3;
        int tRow = 0;
        int tCol = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                tRow = row * 3 + i;
                tCol = col * 3 + j;
                if (row != tRow && col != tCol) {
                    res = res.replace(board[tRow][tCol] + "", "");
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution_37 solution_37 = new Solution_37();
        char[][] grid = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solution_37.solveSudoku(grid);
        System.out.println("grid = " + grid);
    }
}
